The off-line group seat reservation problem

In this paper we address the problem of assigning seats in a train for a group of people traveling together. We consider two variants of the problem. One is a special case of two-dimensional knapsack where we consider the train as having fixed size and the objective is to maximize the utilization of the seats in the train. The second is a special case of two-dimensional bin packing where all requests must be accommodated while trying to minimize the number of passenger cars needed. For both variants of the problem we present a number of bounds and develop exact algorithms. Computational results are presented for various instances based on realistic data, and from the packing literature adapted to the problems addressed.     

A hypersingular integral equation for the floating body problem

A new boundary integral equation formulation for the floating body problem, which is defined on a bounded domain and includes a hypersingular and a nonlocal part, is proved to satisfy a Gärding inequality. Under the assunlption of uniqueness it is shown, that an approximating sequence of related semidiscrete integral operators is uniformly bounded invertible.     

Biorthogonal Rational Functions and the Generalized Eigenvalue Problem

We present some general results concerning so-called biorthogonal polynomials of R_II type introduced by M. Ismail and D. Masson. These polynomials give rise to a pair of rational functions which are biorthogonal with respect to a linear functional. It is shown that these rational functions naturally appear as eigenvectors of the generalized eigenvalue problem for two arbitrary tri-diagonal matrices. We study spectral transformations of these functions leading to a rational modification of the linear functional. An analogue of the Christoffel–Darboux formula is obtained.     

A Homological Approach to Two Problems on Finite Sets

We propose a homological approach to two conjectures descended from the Erdös-Ko-Rado Theorem, one due to Chvátal and the other to Frankl and Füredi. We apply the method to reprove, and in one case improve, results of these authors related to their conjectures.     

Investigation and application of point implicit Runge–Kutta methods to inviscid flow problems

We derive and investigate point implicit Runge–Kutta methods to significantly improve the convergence rate to approximate steady‐state solutions of inviscid flows. It turns out that the point implicit Runge–Kutta can be interpreted as a preconditioned explicit Runge–Kutta method, where the preconditioner arises naturally as local derivative of the residual function. Moreover, many preconditioners suggested in the literature so far are identified as special case of our general ansatz. Conditions will be formulated such that explicit Runge–Kutta methods with local time stepping are equivalent to point implicit methods. In numerical examples, we will demonstrate the improved convergence rates. Copyright © 2011 John Wiley & Sons, Ltd.     

A dual‐weighted trust‐region adaptive POD 4‐D Var applied to a finite‐volume shallow water equations model on the sphere

In this paper we study solutions of an inverse problem for a global shallow water model controlling its initial conditions specified from the 40‐yr ECMWF Re‐analysis (ERA‐40) data sets, in the presence of full or incomplete observations being assimilated in a time interval (window of assimilation) with or without background error covariance terms. As an extension of the work by Chen et al. (Int. J. Numer. Meth. Fluids 2009), we attempt to obtain a reduced order model of the above inverse problem, based on proper orthogonal decomposition (POD), referred to as POD 4D‐Var for a finite volume global shallow water equation model based on the Lin–Rood flux‐form semi‐Lagrangian semi‐implicit time integration scheme. Different approaches of POD implementation for the reduced inverse problem are compared, including a dual‐weighted method for snapshot selection coupled with a trust‐region POD adaptivity approach. Numerical results with various observational densities and background error covariance operator are also presented. The POD 4‐D Var model results combined with the trust‐region adaptivity exhibit similarity in terms of various error metrics to the full 4D Var results, but are obtained using a significantly lesser number of minimization iterations and require lesser CPU time. Based on our previous and current work, we conclude that POD 4‐D Var certainly warrants further studies, with promising potential of its extension to operational 3‐D numerical weather prediction models. Copyright © 2011 John Wiley & Sons, Ltd.     

Reconstruction of Hp -Functions: Best Approximation,Regularization and Optimal Error Estimates

Let U be the open unit disc of the complex plane. We explicitly construct the best pointwise approximation for determining a function in the Hardy space H ^p (U) from measured data at a countable set of points in U whenever the data is exact. A regularization scheme is given to deal with the case of nonexact data. Moreover, optimal error estimates are also studied.     

Accuracies and conservation errors of various ghost fluid methods for multi-medium Riemann problem

Since the (original) ghost fluid method (OGFM) was proposed by Fedkiw et al. in 1999 [5], a series of other GFM-based methods such as the gas–water version GFM (GWGFM), the modified GFM (MGFM) and the real GFM (RGFM) have been developed subsequently. Systematic analysis, however, has yet to be carried out for the various GFMs on their accuracies and conservation errors. In this paper, we develop a technique to rigorously analyze the accuracies and conservation errors of these different GFMs when applied to the multi-medium Riemann problem with a general equation of state (EOS). By analyzing and comparing the interfacial state provided by each GFM to the exact one of the original multi-medium Riemann problem, we show that the accuracy of interfacial treatment can achieve “third-order accuracy” in the sense of comparing to the exact solution of the original mutli-medium Riemann problem for the MGFM and the RGFM, while it is of at most “first-order accuracy” for the OGFM and the GWGFM when the interface approach is actually near in balance. Similar conclusions are also obtained in association with the local conservation errors. A special test method is exploited to validate these theoretical conclusions from the numerical viewpoint.     

A penalized Fischer-Burmeister NCP-function

We introduce a new NCP-function in order to reformulate the nonlinear complementarity problem as a nonsmooth system of equations. This new NCP-function turns out to have stronger theoretical properties than the widely used Fischer-Burmeister function and other NCP-functions suggested previously. Moreover, numerical experience indicates that a semismooth Newton method based on this new NCP-function performs considerably better than the corresponding method based on the Fischer-Burmeister function. Received: March 10, 1997 / Accepted: February 15, 2000?Published online May 12, 2000